package zuoshen_video;

import java.util.*;

import org.junit.Test;

import utils.BracketUtils;
public class DynamicProgramingProblems {
    class BackpackProblem {
        //背包的体积为n，将最大价值的物品放入背包
        //weight：体积数组； value：价值数组
        public int one_zero(int[] weight, int[] value, int n) {
            int len = weight.length;
            //第一维：考虑放不放入第i
            //第二维：此时背包的体积，n表示一件都不放
            int[][] f = new int[len][n + 1];
            f[0][n] = 0; //表示一件物品都没放入，因此价值也为0

            for (int i = 1; i < len; i++) {
                for (int j = n; j >= weight[i]; j--) {
                    //从i - 1状态转化而来
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i]);
                }
            }

            return f[len][n];
        } 

        public int one_zero2(int[] weight, int[] value, int n) {
            int len = weight.length;
            //第一维：考虑放不放入第i
            //第二维：此时背包的体积，n表示一件都不放
            int[] f = new int[n + 1];
            f[n] = 0; //表示一件物品都没放入，因此价值也为0

            for (int i = 1; i < len; i++) {
                for (int j = n; j >= weight[i]; j--) {
                    //从i - 1状态转化而来
                    f[j] = Math.max(f[j], f[j - weight[i]] + value[i]);
                }
            }

            return f[n];
        } 
    }

    class VolantRecursion {
        //1.honni塔问题
        public void move(int n, String from, String to, String help) {
            if (n == 1) {
                System.out.println("将第1个盘子从" + from + "移动到" + to);
                return;
            }
            move(n - 1, from, help, to);
            System.out.println("将第" + n + "个盘子从" + from + "移动到" + to);
            move(n - 1, help, to, from);
        }
    }


    class RecursionToDynamicX {
        public boolean canGetTarget1(int[] nums, int target) {
            map = new HashMap<>();
            return dfs(nums, target);
        }
        Map<Integer, Boolean> map;
        public boolean dfs(int[] nums, int target/* , Queue<Integer> cur */) {
            if (target == 0) return true;
            if (map.containsKey(target)) return map.get(target);
            boolean res = false;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= target) {
                    res = res || dfs(nums, target - nums[i]);
                    if (res) return true;
                } 
            }
            map.put(target, res);
            return res;
        }

        public boolean canGetTarget2(int[] nums, int target) {
            //变化的量， i， target f[i]表示选不选择第i个？
            int len = nums.length;
            boolean f[][] = new boolean[len][target + 1];
          //用nums[i]去获得target = ?
            for (int i = 0; i <= target;i++) {
               f[0][i] = nums[0] == i;
            }
            for (int i = 1; i < nums.length; i++) {
                for (int j = 0; j <= target; j++) {
                    f[i][j] = f[i - 1][j];
                    if (nums[i] <= j) {
                        f[i][j] = f[i][j] || f[i - 1][j - nums[i]];
                    }
                }
            }
            boolean res = false;
            for (int i = 0;i < len; i++) {
                res = res || f[i][target];
            }
            return res;
        }

        public boolean canGetTarget(int[] nums, int target) {
            //变化的量， i， target f[i]表示选不选择第i个？
            int len = nums.length;
            boolean f[] = new boolean[target + 1];
          //用nums[i]去获得target = ?
            for (int i = 0; i <= target;i++) {
               f[0] = nums[i] == 0;
               if (f[0]) break;
            }
            for (int i = 1; i < nums.length; i++) {
                for (int j = target; j >= 0; j--) {
                    if (nums[i] <= j) {
                        f[j] = f[j] || f[j - nums[i]];
                    }
                }
            }

         return f[target];
        }
    }

    //类背包问题的获取target，每个位置只能拿一次
    class RecursionToDynamic {
        public boolean getTarget(int[] nums, int target) {
            return dfs(nums, 0, target, 0);
        }
        int[][] p;
        public boolean dfs(int[] nums, int sum, int target, int idx) {
            if (idx == nums.length) return sum == target;
            // if (map.get(n))  变量 sum + idx， 无法变成记忆化递归,但是由于sum 和 idx都是数字，可以变成二维数组存取，因此可以使用动态规划
            return dfs(nums, sum + nums[idx], target, idx + 1) || dfs(nums, sum, target, idx + 1);
        }

        public boolean getTargetDynamic(int[] nums, int target) {
            int sum = 0, len = nums.length;
            for (int i = 0; i < len; i++) sum += nums[i];
            boolean[][] f = new boolean[len + 1][sum + 1];
            f[len][target] = true;//只有sum == target为true，其他默认为false

            for (int i = len - 1; i >= 0; i--) {
                for (int j = 0; j <= sum; j++) {
                    f[i][j] = f[i + 1][j];
                    if (j + nums[i] <= sum) f[i][j] = f[i][j] || f[i + 1][j + nums[i]];
                }
            }
            return f[0][0];
        }
        public boolean getTargetDynamic2(int[] nums, int target) {
            int sum = 0, len = nums.length;
            for (int i = 0; i < len; i++) sum += nums[i];
            if (sum < target) return false;
            boolean[] f = new boolean[sum + 1];
            f[target] = true;//只有sum == target为true，其他默认为false
            for (int i = len - 1; i >= 0; i--) {
                for (int j = 0; j <= sum; j++) {
                    if (j + nums[i] <= sum) f[j] = f[j] || f[j + nums[i]];
                }
            }
            return f[0];
        }
    }

    @Test
    public void test1() {
        RecursionToDynamic rtd = new RecursionToDynamic();
        int[] nums = {3, 2, 5};
        int target = 4;
        boolean res = rtd.getTargetDynamic2(nums, target);
        System.out.println(res);
    }

     class PathProblem{
        public  int dfs(int i, int j, int[][] nums) {
            int m = nums.length, n = nums[0].length; 
            if (i == m - 1 && j == n - 1) return 1;
            if (i == m - 1) return /* dfs(i, j + 1, nums); */1;
            if (j == n - 1) return /* dfs(i + 1, j, nums); */1;
            return dfs(i, j + 1, nums) + dfs(i + 1, j,nums);
        }

        //改为动态规划
        //1.所求目标：(0, 0) -> (m - 1, n - 1)
        //2.可以直接得到的解 i或者j有一个达到了边缘 -> (m - 1, n - 1) ： 只有1条路走
        //3.普通： 可以走两条路径达到(m - 1, n - 1),即先走到右边，或者先走到上面，在走到(m - 1, n - 1)

        /* 
            i, j为变量，即动态规划表格的两个维度
            其大小为这两个状态所能取得的最大值

            f[i][j] 表示从(i, j) -> (m - 1, n - 1)的路径数
            i == m - 1 || j == n - 1直接得到解
        */

        public int dfsToDyn(int m, int n) {
            int[][] f = new int[m][n];
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    if (i == m - 1 || j == n - 1) f[i][j] = 1;
                    else f[i][j] = f[i + 1][j] + f[i][j + 1];
                }
            }
            BracketUtils.printArray(f);
            return f[0][0];
        }
    }

    @Test
    public void test2() {
        PathProblem pp = new PathProblem();
        int nums[][] = new int[4][4];
        System.out.println(pp.dfs(0, 0, nums));
        System.out.println(pp.dfsToDyn(4, 4));
    }

    @Test
    public void test() {
        VolantRecursion vr = new VolantRecursion();
        vr.move(3, "左", "右", "中");
    }

  
}
